import java.util.LinkedList;
import java.util.Queue;

/**
 * 200 岛屿的数量
 *
 * 1020 飞地的数量
 *
 * 130 被围绕的区域
 *
 * 733 图像渲染
 *
 * 1034 边框着色
 *
 * 529 扫雷游戏
 *
 * 827 最大人工岛屿
 *
 * 1091 二进制矩阵中的最短路径
 *
 * @Author: dust
 * @Date: 2019/11/19 16:07
 */
class Solution {

    private  boolean[] visited;
    private  int[] colors;
    private  int flag=-1;
    private  boolean result=true;
    public  boolean isBipartite(int[][] graph) {
        visited=new boolean[graph.length];
        colors=new int[graph.length];

        for(int i=0;i<graph.length;i++){
            for(int j=0;j<visited.length;j++){
                visited[j]=false;
                colors[j]=0;
            }
            if(!bfs(i,graph)){
                result=false;
            }
        }
        return result;
    }

    public  boolean bfs(int v,int[][]graph){
        Queue<Integer> queue=new LinkedList<>();
        queue.add(v);
        visited[v]=true;
        colors[v]=flag;
        while(!queue.isEmpty()){
            int t=queue.remove();
            flag=-colors[t];
            for(int w:graph[t]){
                if(visited[w]==false){
                    visited[w]=true;
                    colors[w]=flag;
                    queue.add(w);
                }else if(colors[w]==colors[t]){
                    return false;
                }
            }
        }
        return true;
    }





    public static void main(String[] args) {
        int[][]graph=new int[][]{{1},{0,3},{3},{1,2}};
//        {},{2,4,6},{1,4,8,9},{7,8},{1,2,8,9},{6,9},{1,5,7,8,9},{3,6,9},{2,3,4,6,9},{2,4,5,6,7,8}
//        Solution.isBipartite(graph);
//        System.out.println(Solution.isBipartite(graph));

    }
}